// Implement with help from Wikipedia: http://en.wikipedia.org/wiki/Disjoint-set_data_structure
// With help from Emil Stefanov @http://www.emilstefanov.net/Projects/DisjointSets.aspx

#ifndef _DISJOINTSETS_H
#define	_DISJOINTSETS_H

#include <vector>
#include "Triangle.h"

class DisjointSets
{
public:

	// Create an empty DisjointSets data structure
	DisjointSets();

	// Destructor
	~DisjointSets();

	// Find the set identifier that an element currently belongs to.
	// Note: some internal data is modified for optimization even though this method is consant.
	int findSet(Triangle * room) const;

	// Combine two sets into one. All elements in those two sets will share the same set id that can be gotten using FindSet.
	void unionSets(Triangle * room1, Triangle * room2);

	// Add a specified number of elements to the DisjointSets data structure. The element id's of the new elements are numbered
	// consequitively starting with the first never-before-used elementId.
	void addElement(Triangle * room);

	// Returns the number of elements currently in the DisjointSets data structure.
	int numElements() const;
        
	// Returns the number of sets currently in the DisjointSets data structure.
	int numSets() const;

private:

	// Internal Node data structure used for representing an element
	struct MazeNode
	{
		int rank; // This roughly represent the max height of the node in its subtree
		int index; // The index of the element the node represents
		MazeNode* parent; // The parent node of the node
                Triangle* room; // The triangle that makes up the room
	};

	int m_numElements; // the number of elements currently in the DisjointSets data structure.
	int m_numSets; // the number of sets currently in the DisjointSets data structure.
	std::vector<MazeNode*> m_nodes; // the list of nodes representing the elements
};


#endif	/* _DISJOINTSETS_H */

